1. Field of the Invention
The invention relates to motion or depth estimation.
2. Description of the Related Art
Block matching has been used with success in video coding applications (see Refs. 3 and 4) for displacement estimation and movement compensation. Block matching algorithms are iterative minimization algorithms which assume that all pixels within a given block move uniformly, say with vector (ij). If, for that block, we minimize the Mean Squared Error (MSE) with respect to (ij), we can find, after convergence, the most likely motion for that block from time t to t+1.
                              MSE          ⁡                      (                          i              ,              j                        )                          =                              1            MN                    ⁢                                    ∑                              m                =                1                            M                        ⁢                                                  ⁢                                          ∑                                  n                  =                  1                                N                            ⁢                                                          ⁢                                                [                                                                                    U                                                  t                          +                          1                                                                    ⁡                                              (                                                  m                          ,                          n                                                )                                                              -                                                                  U                        t                                            ⁡                                              (                                                                              m                            +                            i                                                    ,                                                      n                            +                            j                                                                          )                                                                              ]                                2                                                                        (        1        )            Here, M,N are the dimensions of the block in pixels. Ut(m,n) is the pixel intensity of a scene at time t, at the location (m,n). The (i,j)'s are taken from a set of candidates: CS. The minimal value of MSE over CS is called the matching penalty (MP).
In a method proposed by G. de Haan in Ref. 5, which we refer in this text as the standard solution or the original algorithm, the candidate set consists of values taken from a given arrangement of neighbors. This known arrangement is optimized to enable an efficient hardware implementation.